/* Foley C# Utilities
 * Copyright (C)2002 Rodney S. Foley
 *  
 * This program is free software; you can 
 * redistribute it and/or modify it under the 
 * terms of the GNU General Public License as 
 * published by the Free Software Foundation; 
 * either version 2 of the License, or (at your 
 * option) any later version.
 * 
 * This program is distributed in the hope that 
 * it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR 
 * PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU 
 * General Public License along with this 
 * program; if not, write to: 
 * 
 *		Free Software Foundation, Inc., 
 *		59 Temple Place, Suite 330, 
 *		Boston, MA 02111-1307 USA
 * 
 *					- or -
 * 
 * http://opensource.org/licenses/gpl-license.php
 */

using System;
using System.Collections;

namespace Foley.Utilities.Collections
{
	/// <summary>
	/// A Hash Set implementation extending the abstract <see cref="SetBase"/> class.
	/// </summary>
	/// <remarks>
	/// For details on how inital capacitys, load factors, hash code providers,
	/// and comparers work please see <see cref="Hashtable"/> for details.
	/// <p>Will not except <c>null</c> objects.</p>
	/// </remarks>
	public class HashSet : SetBase, ICloneable
	{
		#region Private Member Variables
		private static readonly object DUMMY = new object();

		private Hashtable table;
		#endregion

		#region Public Constructors
		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that is empty.
		/// </summary>
		public HashSet()
		{
			table = new Hashtable();
		}

		/// <summary>
		/// Creates an empty <see cref="HashSet"/> with the specified initial capacity and 
		/// using the default load factor, the default hash code provider 
		/// and the default comparer.
		/// </summary>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can initially contain.
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// </exception>
		public HashSet(int initialCapacity)
		{
			table = new Hashtable(initialCapacity);
		}

		/// <summary>
		/// Creates an empty <see cref="HashSet"/> with the specified initial capacity and 
		/// using the specified load factor, the default hash code provider 
		/// and the default comparer.
		/// </summary>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can 
		/// initially contain.
		/// </param>
		/// <param name="loadFactor">
		/// A number in the range from 0.1 through 1.0 indicating 
		/// the maximum ratio of elements to buckets.
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is less than 0.1.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is greater than 1.0.
		/// </exception>
		public HashSet(int initialCapacity, float loadFactor)
		{
			table = new Hashtable(initialCapacity, loadFactor);
		}

		/// <summary>
		/// Creates an empty <see cref="HashSet"/> with the default initial capacity and 
		/// using the default load factor, the specified hash code provider 
		/// and the specified comparer.
		/// </summary>
		/// <param name="hcp">
		/// The <see cref="IHashCodeProvider"/> that supplies the hash codes for all 
		/// elements in the <see cref="HashSet"/>. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// hash code provider, which is each element's implementation of 
		/// <see cref="object.GetHashCode"/>.
		/// </param>
		/// <param name="comparer">
		/// The <see cref="IComparer"/> to use to determine whether two elements are equal. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// comparer, which is each element's implementation of <see cref="object.Equals"/>. 
		/// </param>
		public HashSet(IHashCodeProvider hcp, IComparer comparer)
		{
			table = new Hashtable(hcp, comparer);
		}

		/// <summary>
		/// Creates an empty <see cref="HashSet"/> with the specified initial capacity and 
		/// using the default load factor, the specified hash code provider 
		/// and the specified comparer.
		/// </summary>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can initially contain.
		/// </param>
		/// <param name="hcp">
		/// The <see cref="IHashCodeProvider"/> that supplies the hash codes for all 
		/// elements in the <see cref="HashSet"/>. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// hash code provider, which is each element's implementation of 
		/// <see cref="object.GetHashCode"/>.
		/// </param>
		/// <param name="comparer">
		/// The <see cref="IComparer"/> to use to determine whether two elements are equal. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// comparer, which is each element's implementation of <see cref="object.Equals"/>. 
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// </exception>
		public HashSet(int initialCapacity, IHashCodeProvider hcp, IComparer comparer)
		{
			table = new Hashtable(initialCapacity, hcp, comparer);
		}

		/// <summary>
		/// Creates an empty <see cref="HashSet"/> with the specified initial capacity and 
		/// using the specified load factor, the specified hash code provider 
		/// and the specified comparer.
		/// </summary>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can 
		/// initially contain.
		/// </param>
		/// <param name="loadFactor">
		/// A number in the range from 0.1 through 1.0 indicating 
		/// the maximum ratio of elements to buckets.
		/// </param>
		/// <param name="hcp">
		/// The <see cref="IHashCodeProvider"/> that supplies the hash codes for all 
		/// elements in the <see cref="HashSet"/>. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// hash code provider, which is each element's implementation of 
		/// <see cref="object.GetHashCode"/>.
		/// </param>
		/// <param name="comparer">
		/// The <see cref="IComparer"/> to use to determine whether two elements are equal. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// comparer, which is each element's implementation of <see cref="object.Equals"/>. 
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is less than 0.1.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is greater than 1.0.
		/// </exception>
		public HashSet(int initialCapacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer)
		{
			table = new Hashtable(initialCapacity, hcp, comparer);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that contains 
		/// elements copied from the specified collection.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are copied to the new list.
		/// </param>
		public HashSet(ICollection collection) : this()
		{
			Add(collection);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that contains 
		/// elements copied from the specified collection with the specified 
		/// initial capacity and using the specified load factor, the 
		/// default hash code provider and the default comparer.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are copied to the new list.
		/// </param>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can initially contain.
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// </exception>
		public HashSet(ICollection collection, int initialCapacity) : this (initialCapacity)
		{
			Add(collection);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that contains 
		/// elements copied from the specified collection with the specified 
		/// initial capacity and using the specified load factor, the 
		/// default hash code provider and the default comparer.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are copied to the new list.
		/// </param>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can initially contain.
		/// </param>
		/// <param name="loadFactor">
		/// A number in the range from 0.1 through 1.0 indicating 
		/// the maximum ratio of elements to buckets.
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is less than 0.1.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is greater than 1.0.
		/// </exception>
		public HashSet(ICollection collection, int initialCapacity, float loadFactor) : this (initialCapacity, loadFactor)
		{
			Add(collection);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that contains 
		/// elements copied from the specified collection with the default 
		/// initial capacity and using the default load factor, the 
		/// specified hash code provider and the specified comparer.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are copied to the new list.
		/// </param>
		/// <param name="hcp">
		/// The <see cref="IHashCodeProvider"/> that supplies the hash codes for all 
		/// elements in the <see cref="HashSet"/>. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// hash code provider, which is each element's implementation of 
		/// <see cref="object.GetHashCode"/>.
		/// </param>
		/// <param name="comparer">
		/// The <see cref="IComparer"/> to use to determine whether two elements are equal. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// comparer, which is each element's implementation of <see cref="object.Equals"/>. 
		/// </param>
		public HashSet(ICollection collection, IHashCodeProvider hcp, IComparer comparer) : this (hcp, comparer)
		{
			Add(collection);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that contains 
		/// elements copied from the specified collection with the specified 
		/// initial capacity and using the default load factor, the 
		/// specified hash code provider and the specified comparer.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are copied to the new list.
		/// </param>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can initially contain.
		/// </param>
		/// <param name="hcp">
		/// The <see cref="IHashCodeProvider"/> that supplies the hash codes for all 
		/// elements in the <see cref="HashSet"/>. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// hash code provider, which is each element's implementation of 
		/// <see cref="object.GetHashCode"/>.
		/// </param>
		/// <param name="comparer">
		/// The <see cref="IComparer"/> to use to determine whether two elements are equal. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// comparer, which is each element's implementation of <see cref="object.Equals"/>. 
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// </exception>
		public HashSet(ICollection collection, int initialCapacity, IHashCodeProvider hcp, IComparer comparer) : this (initialCapacity, hcp, comparer)
		{
			Add(collection);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="HashSet"/> class that contains 
		/// elements copied from the specified collection with the specified 
		/// initial capacity and using the specified load factor, the 
		/// specified hash code provider and the specified comparer.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are copied to the new list.
		/// </param>
		/// <param name="initialCapacity">
		/// The approximate number of elements that the <see cref="HashSet"/> can 
		/// initially contain.
		/// </param>
		/// <param name="loadFactor">
		/// A number in the range from 0.1 through 1.0 indicating 
		/// the maximum ratio of elements to buckets.
		/// </param>
		/// <param name="hcp">
		/// The <see cref="IHashCodeProvider"/> that supplies the hash codes for all 
		/// elements in the <see cref="HashSet"/>. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// hash code provider, which is each element's implementation of 
		/// <see cref="object.GetHashCode"/>.
		/// </param>
		/// <param name="comparer">
		/// The <see cref="IComparer"/> to use to determine whether two elements are equal. 
		/// <P>-or-</P>
		/// A <c>null</c> reference (Nothing in Visual Basic) to use the default 
		/// comparer, which is each element's implementation of <see cref="object.Equals"/>. 
		/// </param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <I>capacity</I> is less than zero.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is less than 0.1.
		/// <P>-or-</P>
		/// <I>loadFactor</I> is greater than 1.0.
		/// </exception>
		public HashSet(ICollection collection, int initialCapacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer)
		{
			Add(collection);
		}
		#endregion

		#region Public Member Properties
		/// <summary>
		/// Gets the number of elements contained in the <see cref="HashSet"/>.
		/// </summary>
		/// <value>
		/// The number of elements actually contained in the <see cref="HashSet"/>.
		/// </value>
		public override int		Count	 { get { return table.Count; } }

		/// <summary>
		/// Gets a value idicating whether the <see cref="HashSet"/> is empty 
		/// or not.
		/// </summary>
		/// <value>
		/// <c>true</c> if the <see cref="HashSet"/> contains no elements; 
		/// otherwise, <c>false</c>.
		/// </value>
		public override bool	IsEmpty	 { get { return table.Count <= 0; } }

		/// <summary>
		/// Gets an <see cref="object"/> that can be used to synchronize 
		/// access to the <see cref="HashSet"/>.
		/// </summary>
		/// <value>
		/// An <see cref="object"/> that can be used to synchronize 
		/// access to the <see cref="HashSet"/>.
		/// </value>
		public override object	SyncRoot { get { return table.SyncRoot; } }
		#endregion

		#region Public Member Methods
		/// <summary>
		/// Adds an <see cref="object"/>
		/// into the <see cref="HashSet"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to be added into 
		/// the <see cref="HashSet"/>
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="HashSet"/> is modified; otherwise <c>false</c>.
		/// </returns>
		/// <exception cref="System.ArgumentNullException">
		/// The <paramref name="value"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public override bool Add(object value)
		{
			bool wasAdded = false;

			if (!table.Contains(value))
			{
				table.Add(value, DUMMY);
				wasAdded = table.Contains(value);
			}
			
			return wasAdded;
		}

		/// <summary>
		/// Adds the elements of an <see cref="ICollection"/> 
		/// into the <see cref="HashSet"/>.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements 
		/// should be added into the <see cref="HashSet"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="HashSet"/> is modified; otherwise <c>false</c>.
		/// </returns>
		/// <exception cref="System.ArgumentNullException">
		/// The <paramref name="collection"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public override bool Add(ICollection collection)
		{
			int countBefore = table.Count;

			foreach (object value in collection)
				if (!table.Contains(value))
					table.Add(value, DUMMY);

			return countBefore != table.Count;
		}

		/// <summary>
		/// Removes all elements from the <see cref="HashSet"/>.
		/// </summary>
		public override void Clear()
		{
			table.Clear();
		}

		/// <summary>
		/// Creates a shallow copy of the <see cref="HashSet"/>.
		/// </summary>
		/// <returns>
		/// A shallow copy of the <see cref="HashSet"/>.
		/// </returns>
		/// <remarks>
		/// If you need a deep copy to be attempted use the
		/// <see cref="HashSet.Clone(bool)"/> method.
		/// </remarks>
		public virtual object Clone()
		{
			HashSet	setClone = new HashSet();
			
			setClone.table = (Hashtable)table.Clone();
			
			return setClone;
		}

		/// <summary>
		/// Attempts to make a deep copy of the <see cref="HashSet"/>.
		/// </summary>
		/// <param name="attemptDeepCopy">
		/// If <c>true</c> will attempt to make a deep copy, 
		/// if <c>false</c> it will just return a shallow copy
		/// </param>
		/// <returns>
		/// The newly cloned <see cref="HashSet"/>.
		/// </returns>
		/// <exception cref="SystemException">
		/// If and <see cref="object"/> in the list is not an 
		/// <see cref="ICloneable"/>.
		/// </exception>
		/// <remarks>
		/// Attempts to make a deep copy if <paramref name="attemptDeepCopy"/> is true.
		/// It will attempt this by checking if an <see cref="object"/> is an 
		/// <see cref="ICloneable"/>, and then defer the process to its Clone method. 
		/// <para>
		/// If a <c>true</c> deep copy is important, please check the API documentation for the
		/// elements that are contained in the list to verify how their <c>Clone</c> method is
		/// implemented.
		/// </para>
		/// </remarks>
		/// <exception cref="SystemException">
		/// At the first <see cref="object"/> that is not an <see cref="ICloneable"/> 
		/// when <paramref name="attemptDeepCopy"/> is true.
		/// </exception>
		public virtual HashSet Clone(bool attemptDeepCopy)
		{
			HashSet setClone;

			if (attemptDeepCopy)
			{
				setClone = new HashSet();

				foreach (object obj in table.Keys)
				{
					if (obj == null)
						setClone.Add(null);
					else if (obj is ICloneable)
						setClone.Add(((ICloneable)obj).Clone());
					else
						throw new SystemException("The object of type [" + obj.GetType() + 
							"] in the set is not an ICloneable, cannot attempt a deep copy.");
				}	
			}
			else
				setClone = (HashSet)this.Clone();

			return setClone;
		}

		/// <summary>
		/// Determines whether an <see cref="object"/> is in the <see cref="HashSet"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to locate in the <see cref="HashSet"/>. 
		/// The <see cref="object"/> to locate can be a <c>null</c> reference (<c>Nothing</c> in Visual Basic). 
		/// </param>
		/// <returns>
		/// <c>true</c> if <paramref name="value"/> is found in the <see cref="HashSet"/>; otherwise, <c>false</c>.
		/// </returns>
		/// <remarks>
		/// This implementation is close to O(1) in most cases.
		/// </remarks>
		/// <exception cref="ArgumentNullException">
		/// The <paramref name="value"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public override bool Contains(object value)
		{
			return table.Contains(value);
		}

		/// <summary>
		/// Determines whether all the elements in the specified 
		/// collection are contained in the <see cref="HashSet"/>.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are to be added
		/// to the end of the <see cref="HashSet"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if all the elements of the <see cref="ICollection"/> are
		/// found in the <see cref="HashSet"/>; otherwise, false.
		/// </returns>
		/// <exception cref="ArgumentNullException">
		/// The <paramref name="collection"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		/// <remarks>
		/// This implementation is close to O(1) in most cases.
		/// </remarks>
		public override bool Contains(ICollection collection)
		{
			bool constainsAll = true;

			foreach (object value in collection)
			{
				if (!Contains(value))
				{
					constainsAll = false;
					break;
				}
			}

			return constainsAll;	
		}

		/// <summary>
		/// Copies the entire <see cref="HashSet"/> to a compatible one-dimensional <see cref="Array"/>, 
		/// starting at the specified <paramref name="index"/> of the target <paramref name="array"/>.
		/// </summary>
		/// <param name="array">
		/// The one-dimensional <see cref="Array"/> that is the destination of the elements
		/// copied from the <see cref="HashSet"/>. The <see cref="Array"/> must have zero-based indexing.
		/// </param>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> in <paramref name="array"/> at which copying begins.
		/// </param>
		/// <exception cref="System.ArgumentNullException">
		/// The <paramref name="array"/> is a <c>null</c> reference (<c>Nothing</c> in Visual Basic).
		/// </exception>
		/// <exception cref="System.ArgumentOutOfRangeException">
		/// The <paramref name="index"/> is less than zero.
		/// </exception>
		/// <exception cref="System.ArgumentException">
		/// The <paramref name="array"/> is multidimensional.
		/// <p>-or-</p>
		/// The <paramref name="index"/> is equal to or greater than the length of <paramref name="array"/>.
		/// <p>-or-</p>
		/// The number of elements in the <see cref="HashSet"/> is greater than
		/// the available space from <paramref name="index"/> to the end of the destination <paramref name="array"/>.
		/// </exception>
		public override void CopyTo(Array array, int index)
		{
			table.Keys.CopyTo(array, index);
		}

		/// <summary>
		/// Returns an <see cref="IEnumerator"/> 
		/// for the entire <see cref="HashSet"/>.
		/// </summary>
		/// <returns>
		/// An <see cref="IEnumerator"/> for the entire <see cref="HashSet"/>.
		/// </returns>
		public override IEnumerator GetEnumerator()
		{
			return table.Keys.GetEnumerator();
		}

		/// <summary>
		/// Removes the occurrence of the specific <see cref="object"/> 
		/// from the <see cref="HashSet"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to remove from the <see cref="HashSet"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the HashSet is modified; otherwise <c>false</c>.
		/// </returns>
		/// <exception cref="ArgumentNullException">
		/// The <paramref name="value"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public override bool Remove(object value)
		{
			int beforeCount = table.Count;

			table.Remove(value);

			return beforeCount != table.Count;
		}
		#endregion
	}
}
